A network coordinate system (NCS) is a scalable network distance prediction solution. There is a plurality of manners of defining a network distance. For example, a network distance may be a network delay, network bandwidth, or another measurable physical quantity. As shown in FIG. 1, a network usually includes a plurality of nodes. In a process of constructing a network coordinate system, each node participating in the construction of the network coordinate system may obtain one or more d-dimension vectors through a small amount of measurement. The one or more d-dimension vectors are coordinates of the node in the network coordinate system. Using an example in which the network coordinate system is a network coordinate system based on a Euclidean model, after coordinates of the plurality of nodes shown in FIG. 1 in the Euclidean coordinate system are determined, the plurality of nodes shown in FIG. 1 may be converted into the Euclidean coordinate system to obtain FIG. 2. Assuming that a network distance represents a network delay between two nodes, a network delay between a node 1 and a node 2 in FIG. 1 can be obtained by calculating a distance between a node 1 and a node 2 in FIG. 2.
The network coordinate system is characterized by high scalability and low measurement overheads and can predict a network distance, for example, information such as a network delay or network bandwidth, between any two nodes, according to a pre-defined calculation rule by using network coordinates of the two nodes. Measurement complexity of a network system including M nodes is O(M), and therefore the network coordinate system can predict network distances, for example, delays or bandwidth, between M(M−1) links through measurement whose complexity is O(M), so as to avoid a large amount of end-to-end measurement. The network coordinate system may be applied to a large-scale distributed network system, and can greatly reduce measurement complexity between nodes.
In some approaches, before a network coordinate system is used, coordinates of nodes in a network system need to be first determined in the network coordinate system. In addition, because a status of the network system dynamically changes, a node in the network coordinate system also needs to update coordinates of the node in the network coordinate system continuously. Specifically, a to-be-positioned node first selects a plurality of reference nodes (for example, 32 reference nodes) and then communicates with the reference nodes, to measure network distances between the to-be-positioned node and the reference nodes, for example, delays or bandwidth between the to-be-positioned node and the reference nodes. Further, the to-be-positioned node also receives coordinates of the reference nodes in the network coordinate system. In this way, the to-be-positioned node can fit coordinates of the to-be-positioned node in the network coordinate system based on the coordinates of the reference nodes in the network coordinate system and the measured network distances.
However, due to impact of factors such as random network delay pollution (that is, a random delay change caused by random fluctuation of network communication), a machine fault, or a measurement error, a network distance measured by the to-be-positioned node usually includes an error value and an outlier value. As a result, the coordinates fitted by the to-be-positioned node are inaccurate, causing a relatively large network distance error during subsequent prediction.